1. Field of the Invention
The invention relates generally to the field of digital data processing systems and more specifically to systems for marking as stale entries in processor cache memory circuits which include data for which the data stored in main memory has been overwritten by other units in the system.
2. Description of the Prior Art
A typical digital data processing system includes three basic elements, namely a processor element, a memory element, and an input/output element. The memory element stored information in addressable storage locations. This information includes both data and instructions for processing the data. The processor element includes one or more digital data processing units, or "processors", each of which causes information to be transferred, or fetched, to it from the memory element, interprets the incoming information as either instructions or data, and processes the data in accordance with the instructions. The results are then stored in addressed locations in the memory element.
The input/output element also communicates with the memory element in order to transfer information into the system and to obtain the processed data from it. Units comprising the input/output element normally operate in accordance with control information supplied to it by the processor element. The control information defines the operation to be performed by the input/output unit. At least one class of operations performed by an input/output unit is the transfer of user information, that is, information used by a user program, between the input/output unit and the memory element. Typical units comprising the input/output element include, for example, printers, teletypewriters, and video display terminals, and may also include secondary information storage devices such as disk or tape storage units.
In addition to functioning as input/output devices, disk storage units and, under some circumstances, tape storage units may also function as part of the memory element. In particular, a memory element typically includes a main memory, whose contents are accessible to the processor relatively quickly but which is generally relatively high-cost storage. Modern main memories are typically implemented using MOS or bipolar semiconductor technology and may provide on the order of a fraction of a megabyte to several tens of megabytes of storage.
On the other hand, the time required to access information stored in disk storage units is much longer than main memory, but the disk units can provide large amounts of storage, on the order of hundreds of megabytes or more, at relatively low cost. In addition, unlike main memory, disk storage is non-volatile, that is, the information is not lost if power is removed. Therefore, disk units are used to provide backup storage for the main memory, that is, to provide storage for information which will not fit into main memory until a program needs it. When a program requires information which is stored on a disk but is not in the main memory, that information is transferred into the main memory. If necessary, the contents of the locations in the main memory into which the information from the disk unit was transferred may be transferred to a disk unit for storage therein before being overwritten by data from the disk.
In many digital data processing systems, the processor (assuming only one processor), mass storage devices and other input/output devices all communicate with a single main memory or only a few main memory modules. This may produce contention for the main memory which can interfere with the processor's ability to quickly obtain information from the main memory. This, in turn, can slow the processor's ability to execute programs. The contention problem is exacerbated if all of the units are connected to a single input/output bus, as all information that is transferred must be transferred over the single bus.
Accordingly, in many modern computer systems, the processor includes a cache memory, which is a small private memory accessible only to the processor which stores information from the most recently-requested locations in main memory and from nearby locations. In typical data processing systems, when the processor requests an item of information from a location in the main memory, it will oftentimes require the contents of adjacent locations shortly thereafter. Accordingly, when the processor is able to request information from the main memory, it requests more than it needs at that immediate time, with the expectation that it will likely need at least some of the remaining information shortly thereafter. When the processor gets the item information it then needs, it can immediately begin using it, and if it turns out that the the processor can use the other information that was received, it will have that information stored in the cache, and will not have to wait until it is obtained from the main memory.
Typically a cache memory is organized into blocks each capable of storing a predetermined amount of information. When information has been retrieved from main memory and loaded into a cache block, that block is assigned an address, termed a "tag". The tag corresponds to the address of the corresponding locations in main memory from which the information was retrieved; thus the blocks of the cache are identified with the locations in the main memory. When the processor requires information, the tags in the cache can be examined to determine whether a block contains the requested information. If one does, the information is obtained from the cache; otherwise, the processor retrieves the information from the main memory.
As has been mentioned, when a disk unit transfers information to the main memory, it may overwrite information which was previously in the main memory. When that occurs, however, if information has been stored in one or more blocks in the cache from those locations in main memory, the information in those blocks is stale, that is, the blocks do not contain copies of the information in the memory.